package cxydmmszl.tmp.t8;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

/**
 * <li style="color: red;">Prob</li>
 * 在其它数都出现k次的数组中找到只出现一次的数
 * <li style="color: green;">Desc</li>
 * 给定一个整型数组arr和一个大于1的整数k。已知arr中只有1个数出现了一次，
 * 其他的数出现k次，请返回出现了1次的数。
 * <li style="color: green;">Input</li>
 * 输入包含两行，第一行包含两个整数n和k，1<=n<=10^5，1 < k <= 100，
 * n代表数组arr的长度，第二行n个整数，代表数组arr，数组arr中每个数都是32位整数。
 * <li style="color: green;">Output</li>
 * 输出一个整数，代表唯一出现1次的数。
 * <li style="color: blue;">Link</li> cd148
 *
 * @author habitplus
 * @since 2021-11-03 16:50
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] ss = br.readLine().split(" ");
        int n = Integer.parseInt(ss[0]);
        int k = Integer.parseInt(ss[1]);
        ss = br.readLine().split(" ");
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(ss[i]);
        }

        int num = findNumOnlyOneTimes(arr, k);
        System.out.println(num);
    }

    /*
        哈希表
     */
    private static int findNumOnlyOneTimes01(int[] arr, int k) {
        if (arr == null || arr.length < 1 || k < 1) return 0;
        HashSet<Integer> setOne = new HashSet<>();
        HashSet<Integer> setMul = new HashSet<>();
        for (int num : arr) {
            if (setMul.contains(num)) continue;
            if (setOne.contains(num)) setMul.add(num);
            else setOne.add(num);
        }

        for (int num : arr) {
            if (!setMul.contains(num)) return num;
        }
        return 0;
    }

    /*
        K 进制数的应用
        原理：每个数重复出现了k次就将这个数化为k进制，然后进行无进位加法，
             即每个数的每个bit等于k时就将该数%k，
             这样当这个数重复出现了k次时，累计无进位和为0，最后只剩出现了一次的那个数
     */
    private static int findNumOnlyOneTimes(int[] arr, int k) {
        if (arr == null || arr.length < 1 || k < 1) return 0;

        // 对于 32 位二进制的整数，转换 k(>=2) 进制的数一定可以存到int[32] 中
        int[] digital = new int[32];

        for (int i= 0; i< arr.length; i++) {
            int[] bit = kSystem(arr[i], k);

            for (int j = 0; j < 32; j++) {
                digital[j] = (digital[j] + bit[j]) % k;
            }
        }

        // 还原 k 进制数的十进制表示形式
        int ans = 0;
        for (int i = 31; i >= 0; i--) {
            ans = ans * k + digital[i];
        }
        return ans;
    }

    /*
        对于 32 位二进制的整数，转换 k(>=2) 进制的数一定可以存到int[32] 中
     */
    private static int[] kSystem(int num, int k) {
        int[] res = new int[32];
        int i = 0;
        while (num != 0) {
            res[i++] = num % k;
            num /= k;
        }
        return res;
    }
}
